﻿#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

vector<int> subtractor(vector<int> num1, vector<int> num2, int scale) {
    if (num1.size() < num2.size()) {
        vector<int> temp = num1;
        num1 = num2;
        num2 = temp;
    }
    else if (num1.size() == num2.size()) {
        for (int i = 0; i < num1.size(); i++) {
            if (num1[i] < num2[i]) {
                vector<int> temp = num1;
                num1 = num2;
                num2 = temp;
                break;
            }
            else if (num1[i] > num2[i]) {
                break;
            }
        }
    }
    
    vector<int> result(num1.size(), 0);

    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());

    for (int i = 0; i < num2.size(); i++) {
        if (num1[i] >= num2[i]) {
            result[i] = num1[i] - num2[i];
        }
        else {
            num1[i + 1] = num1[i + 1] - 1;
            result[i] = scale + num1[i] - num2[i];
        }
    }

    for (int i = num2.size(); i < num1.size(); i++) {
        result[i] = num1[i];
    }

    reverse(result.begin(), result.end());

    while (result.size() > 1 && result.back() == 0) {
        result.pop_back();
    }

    return result;
}

void justTest() {
    cout << "test";
}

vector<vector<int>> exploreKaprekar(vector<int> num, int scale) {
    map<vector<int>, int> history;
    vector<int> current = num;
    vector<vector<int>> sequence;

    int step = 0;

    while (history.find(current) == history.end()) {
        history[current] = step;
        sequence.push_back(current);
        vector<int> numMax = current;
        vector<int> numMin = current;

        sort(numMax.begin(), numMax.end(), greater<int>());
        sort(numMin.begin(), numMin.end());

        current = subtractor(numMax, numMin, scale);
        step++;

        if (current.empty() || current == numMax || current == numMin) {
            break;
        }
    }

    // 当发现重复时，截取并返回循环部分
    if (history.find(current) != history.end()) {
        return vector<vector<int>>(sequence.begin() + history[current], sequence.end());
    }

    // 如果未找到循环，则返回整个序列
    return sequence;
}

int main() {
    int scale = 10;
    int amount= 4;

    cout << "输入进制:";
    cin >> scale;
    cout << "输入这个数字的位数:";
    cin >> amount;
    vector<int> num(amount, 0);

    cout << "按照位数输入这个数字:" << endl;
    for (int i = 0; i < amount; i++) {
        cout << "第" << amount - i << "位:";
        cin >> num[i];
    }

    cout << "数字 ";
    for (int i = 0; i < amount; i++) {
        cout << num[i];
    }

    vector<vector<int>> result_sequence = exploreKaprekar(num, scale);

    cout << " 基于 " << scale << " 进制的卡布列克序列11212: ";
    for (auto& num : result_sequence) {
        for (int digit : num) {
            cout << digit;
        }
        cout << " ";
    }
    cout << endl;

    justTest;

    system("pause");

    return 0;
}